package nl.unimaas.games.tron.player.mcts;

import java.io.Serializable;

import java.util.ArrayList;
import java.util.Random;
import nl.unimaas.games.tron.engine.Board;
import nl.unimaas.games.tron.util.KnuthRandom;
import nl.unimaas.games.tron.util.LGRTables;
import nl.unimaas.games.tron.util.NGram;

/**
 * 
 * @author Cliff Laschet
 */
@SuppressWarnings("serial")
public interface SelectionStrategy extends Serializable {

    public Node getNode(Node node);
    public final static SelectionStrategy RANDOM = new SelectionStrategy() {

        @Override
        public Node getNode(Node node) {
            if (node.children.size() > 0) {
                return node.children.get(KnuthRandom.nextInt(node.children.size()));
            } else {
                return null;
            }
        }

        @Override
        public String toString() {
            return "random";
        }
    };

    public static class UCT implements SelectionStrategy {

        protected double C = 10;
        protected int T = 30;
        protected double eps = 1E-10;

        public UCT(double C, int T) {
            this.C = C;
            this.T = T;
        }

        @Override
        public Node getNode(Node node) {
            if (node.visits < T) {
                return SelectionStrategy.RANDOM.getNode(node);
            }
            Node bestNode = null;
            double bestValue = Double.NEGATIVE_INFINITY;
            for (Node n : node.children) {
                double uct = n.value / (n.visits + 1.0) + C * Math.sqrt(Math.log(node.visits + 1.0) / (n.visits + 1.0));

                if (uct > bestValue) {
                    bestNode = n;
                    bestValue = uct;
                }
            }
            return bestNode;
        }

        @Override
        public String toString() {
            return "UCT";
        }
    }

    public static class BiasedUCT implements SelectionStrategy {

        protected double C = 10;
        protected int T = 30;
        protected double W = 10;

        public BiasedUCT(double C, int T, double W) {
            this.C = C;
            this.T = T;
            this.W = W;
        }

        @Override
        public Node getNode(Node node) {
            //if (node.visits < T)
            //	return SelectionStrategy.RANDOM.getNode(node);
            Node bestNode = null;
            double bestValue = Double.NEGATIVE_INFINITY;
            for (Node n : node.children) {
                double pb = 0;
                if (node.move != Board.MOVE_NONE) {
                    pb = (W * (Double) n.tag) / (n.visits - n.draws - n.wins + 1.0);
                }
                double uct = n.value / (n.visits + 1.0) + C * Math.sqrt(Math.log(node.visits + 1.0) / (n.visits + 1.0)) + pb;

                if (uct > bestValue) {
                    bestNode = n;
                    bestValue = uct;
                }
            }
            return bestNode;
        }

        @Override
        public String toString() {
            return "BiasedUCT";
        }
    }

    /**
     * 
     */
    public static class HeuristicUCT implements SelectionStrategy {

        protected double C = 10;
        protected int T = 30;

        public HeuristicUCT(double C, int T) {
            this.C = C;
            this.T = T;
        }

        @Override
        public Node getNode(Node node) {
            //if (node.visits < T)
            //	return SelectionStrategy.RANDOM.getNode(node);
            Node bestNode = null;
            double bestValue = Double.NEGATIVE_INFINITY;
            for (Node n : node.children) {
                double pb = 0;
                if (node.move != Board.MOVE_NONE) {
                    double H = (Double) n.tag;
                    pb = H / (n.visits + 1.0);
                }

                double uct = n.value / (n.visits + 1.0) + C * Math.sqrt(Math.log(node.visits + 1.0) / (n.visits + 1.0));
                //if (pb != 0)
                //System.out.println("pb: " + pb + "  uct: " + uct);
                uct += pb;
                if (uct > bestValue) {
                    bestNode = n;
                    bestValue = uct;
                }
            }
            return bestNode;
        }

        @Override
        public String toString() {
            return "HeuristicUCT";
        }
    }

    public static class NGramRandomSelection implements SelectionStrategy {

        private NGram ngram;
        private double alpha;
        private Random rnd = new Random();
        private boolean syncMoves;

        public NGramRandomSelection(NGram nGram, boolean syncMoves) {
            this.ngram = nGram;
            this.syncMoves = syncMoves;
        }

        @Override
        public Node getNode(Node node) {
            boolean unvisitedLegalMoves = false;

            for (int i = 0; i < node.children.size(); i++) {
                if (node.children.get(i).visits == 0) {
                    unvisitedLegalMoves = true;
                }
            }

            if (unvisitedLegalMoves) {
                int firstMove = -1, secondMove = -1;
                if (this.syncMoves) {
                    if (node.depth % 2 == 0) {
                        if (node.parent != null) {
                            if (node.parent.parent != null) {
                                secondMove = node.parent.parent.playerPosition;
                                if (node.parent.parent.parent != null) {
                                    firstMove = node.parent.parent.parent.playerPosition;
                                }
                            }

                        }
                    } else {
                        secondMove = node.playerPosition;
                        if (node.parent != null) {
                            if (node.parent.parent != null) {
                                if (node.parent.parent.parent != null) {
                                    firstMove = node.parent.parent.parent.playerPosition;
                                }
                            }
                        }
                    }
                } else {
                    if (node.parent != null) {
                        firstMove = node.parent.playerPosition;
                    }
                    secondMove = node.playerPosition;
                }

                ArrayList<Integer> validMoves = new ArrayList<Integer>();
                for (int i = 0; i < node.children.size(); i++) {
                    if (node.children.get(i).visits == 0) {
                        validMoves.add(node.children.get(i).playerPosition);
                    }
                }

                int move = -1;
                if (firstMove != -1 && secondMove != -1) {
                    move = ngram.getAvgPosition(firstMove, secondMove, validMoves);
                    for (int i = 0; i < node.children.size(); i++) {
                        if (node.children.get(i).playerPosition == move) {
                            return node.children.get(i);
                        }
                    }
                }
            }

            //If the above did not decide upon which move to make, apply random selection.
            return SelectionStrategy.RANDOM.getNode(node);
        }
        
        @Override
        public String toString() {
            return "NGramRandom";
        }
    }

    /**
     * 
     */
    public static class NGramUCTSelection implements SelectionStrategy {

        private NGram ngram;
        private double C;
        private int T;
        private SelectionStrategy.UCT uct;
        private boolean syncMoves;

        public NGramUCTSelection(NGram ngram, double C, int T, boolean syncMoves) {
            this.ngram = ngram;
            this.C = C;
            this.T = T;
            this.uct = new SelectionStrategy.UCT(C, T);
            this.syncMoves = syncMoves;
        }

        public Node getNode(Node node) {
            boolean unvisitedLegalMoves = false;

            for (int i = 0; i < node.children.size(); i++) {
                if (node.children.get(i).visits == 0) {
                    unvisitedLegalMoves = true;
                }
            }

            if (unvisitedLegalMoves) {
                int firstMove = -1, secondMove = -1;
                if (this.syncMoves) {
                    if (node.depth % 2 == 0) {
                        if (node.parent != null) {
                            if (node.parent.parent != null) {
                                secondMove = node.parent.parent.playerPosition;
                                if (node.parent.parent.parent != null) {
                                    firstMove = node.parent.parent.parent.playerPosition;
                                }
                            }

                        }
                    } else {
                        secondMove = node.playerPosition;
                        if (node.parent != null) {
                            if (node.parent.parent != null) {
                                if (node.parent.parent.parent != null) {
                                    firstMove = node.parent.parent.parent.playerPosition;
                                }
                            }
                        }
                    }
                } else {
                    if (node.parent != null) {
                        firstMove = node.parent.playerPosition;
                    }
                    secondMove = node.playerPosition;
                }

                ArrayList<Integer> validMoves = new ArrayList<Integer>();
                for (int i = 0; i < node.children.size(); i++) {
                    if (node.children.get(i).visits == 0) {
                        validMoves.add(node.children.get(i).playerPosition);
                    }
                }

                int move = -1;
                if (firstMove != -1 && secondMove != -1) {
                    move = ngram.getAvgPosition(firstMove, secondMove, validMoves);
                    for (int i = 0; i < node.children.size(); i++) {
                        if (node.children.get(i).playerPosition == move) {
                            return node.children.get(i);
                        }
                    }
                }
            }

            //If the above did not decide upon which move to make, apply UCT
            return this.uct.getNode(node);
        }
        
        @Override
        public String toString() {
            return "NGramUCT";
        }
    }

    public static class NGramPBUCTSelection implements SelectionStrategy {

        protected double C = 10;
        protected int T = 30;
        protected double W = 10;
        protected boolean syncMoves;
        protected NGram ngram;

        public NGramPBUCTSelection(NGram ngram, double C, int T, double W, boolean syncMoves) {
            this.ngram = ngram;
            this.C = C;
            this.T = T;
            this.W = W;
            this.syncMoves = syncMoves;
        }

        @Override
        public Node getNode(Node node) {
            Node bestNode = null;
            double bestValue = Double.NEGATIVE_INFINITY;
            for (Node n : node.children) {
                double pb = 0;
                if (node.move != Board.MOVE_NONE) {
                    int firstMove = -1, secondMove = -1;
                    //First, get the firstMove and secondMove, depending on syncMoves
                    if (this.syncMoves) {
                        if (node.depth % 2 == 0) {
                            if (node.parent != null) {
                                if (node.parent.parent != null) {
                                    secondMove = node.parent.parent.playerPosition;
                                    if (node.parent.parent.parent != null) {
                                        firstMove = node.parent.parent.parent.playerPosition;
                                    }
                                }

                            }
                        } else {
                            secondMove = node.playerPosition;
                            if (node.parent != null) {
                                if (node.parent.parent != null) {
                                    if (node.parent.parent.parent != null) {
                                        firstMove = node.parent.parent.parent.playerPosition;
                                    }
                                }
                            }
                        }
                    } else {
                        if (node.parent != null) {
                            firstMove = node.parent.playerPosition;
                        }
                        secondMove = node.playerPosition;
                    }

                    //Set up a list with all the validmoves.
                    ArrayList<Integer> validMoves = new ArrayList<Integer>();
                    for (int i = 0; i < node.children.size(); i++) {
                            validMoves.add(node.children.get(i).playerPosition);
                    }

                    //Get the heuristic value for this situation.
                    int move = -1;
                    if (firstMove != -1 && secondMove != -1) {
                        pb = (W * this.ngram.getHeuristicValue(firstMove, secondMove, n.playerPosition)) / (n.visits - n.draws - n.wins + 1.0);
                    }                   
                }
                double uct = n.value / (n.visits + 1.0) + C * Math.sqrt(Math.log(node.visits + 1.0) / (n.visits + 1.0)) + pb;

                if (uct > bestValue) {
                    bestNode = n;
                    bestValue = uct;
                }
            }
            return bestNode;
        }

        @Override
        public String toString() {
            return "NGramPBUCT";
        }
    }

    public static class LGRRandomSelection implements SelectionStrategy {

        private LGRTables tables;
        private Random rnd = new Random();
        private boolean syncMoves;

        public LGRRandomSelection(LGRTables tables, boolean syncMoves) {
            this.tables = tables;
            this.syncMoves = syncMoves;
        }

        @Override
        public Node getNode(Node node) {
            boolean unvisitedLegalMoves = false;

            for (int i = 0; i < node.children.size(); i++) {
                if (node.children.get(i).visits == 0) {
                    unvisitedLegalMoves = true;
                }
            }

            if (unvisitedLegalMoves) {
                int firstMove = -1, secondMove = -1;
                if (this.syncMoves) {
                    if (node.depth % 2 == 0) {
                        if (node.parent != null) {
                            if (node.parent.parent != null) {
                                secondMove = node.parent.parent.playerPosition;
                                if (node.parent.parent.parent != null) {
                                    firstMove = node.parent.parent.parent.playerPosition;
                                }
                            }

                        }
                    } else {
                        secondMove = node.playerPosition;
                        if (node.parent != null) {
                            if (node.parent.parent != null) {
                                if (node.parent.parent.parent != null) {
                                    firstMove = node.parent.parent.parent.playerPosition;
                                }
                            }
                        }
                    }
                } else {
                    if (node.parent != null) {
                        firstMove = node.parent.playerPosition;
                    }
                    secondMove = node.playerPosition;
                }

                ArrayList<Integer> validMoves = new ArrayList<Integer>();
                for (int i = 0; i < node.children.size(); i++) {
                    if (node.children.get(i).visits == 0) {
                        validMoves.add(node.children.get(i).playerPosition);
                    }
                }

                int move = -1;
                if (firstMove != -1 && secondMove != -1) {
                    move = tables.getLGR2Position(node.children.get(0).playerNr, firstMove, secondMove, validMoves);
                    for (int i = 0; i < node.children.size(); i++) {
                        if (node.children.get(i).playerPosition == move) {
                            return node.children.get(i);
                        }
                    }
                }
            }

            //If the above did not decide upon which move to make, apply random selection.
            return SelectionStrategy.RANDOM.getNode(node);
        }
        
        @Override
        public String toString() {
            return "LGRRandom";
        }
    }

    public static class LGRUCTSelection implements SelectionStrategy {

        private LGRTables tables;
        private double C;
        private int T;
        private SelectionStrategy.UCT uct;
        private boolean syncMoves;

        public LGRUCTSelection(LGRTables tables, double C, int T, boolean syncMoves) {
            this.tables = tables;
            this.C = C;
            this.T = T;
            this.uct = new SelectionStrategy.UCT(C, T);
            this.syncMoves = syncMoves;
        }

        public Node getNode(Node node) {
            boolean unvisitedLegalMoves = false;

            for (int i = 0; i < node.children.size(); i++) {
                if (node.children.get(i).visits == 0) {
                    unvisitedLegalMoves = true;
                }
            }

            if (unvisitedLegalMoves) {
                int firstMove = -1, secondMove = -1;
                if (this.syncMoves) {
                    if (node.depth % 2 == 0) {
                        if (node.parent != null) {
                            if (node.parent.parent != null) {
                                secondMove = node.parent.parent.playerPosition;
                                if (node.parent.parent.parent != null) {
                                    firstMove = node.parent.parent.parent.playerPosition;
                                }
                            }

                        }
                    } else {
                        secondMove = node.playerPosition;
                        if (node.parent != null) {
                            if (node.parent.parent != null) {
                                if (node.parent.parent.parent != null) {
                                    firstMove = node.parent.parent.parent.playerPosition;
                                }
                            }
                        }
                    }
                } else {
                    if (node.parent != null) {
                        firstMove = node.parent.playerPosition;
                    }
                    secondMove = node.playerPosition;
                }

                ArrayList<Integer> validMoves = new ArrayList<Integer>();
                for (int i = 0; i < node.children.size(); i++) {
                    if (node.children.get(i).visits == 0) {
                        validMoves.add(node.children.get(i).playerPosition);
                    }
                }

                int move = -1;
                if (firstMove != -1 && secondMove != -1) {
                    move = tables.getLGR2Position(node.children.get(0).playerNr, firstMove, secondMove, validMoves);
                    for (int i = 0; i < node.children.size(); i++) {
                        if (node.children.get(i).playerPosition == move) {
                            return node.children.get(i);
                        }
                    }
                }
            }

            //If the above did not decide upon which move to make, apply UCT
            return this.uct.getNode(node);
        }
        
        @Override
        public String toString() {
            return "LGRUCT";
        }
    }
    
    public static class LGRPBUCTSelection implements SelectionStrategy {

        protected double C = 10;
        protected int T = 30;
        protected double W = 10;
        protected boolean syncMoves;
        protected LGRTables tables;

        public LGRPBUCTSelection(LGRTables tables, double C, int T, double W, boolean syncMoves) {
            this.tables = tables;
            this.C = C;
            this.T = T;
            this.W = W;
            this.syncMoves = syncMoves;
        }

        @Override
        public Node getNode(Node node) {
            Node bestNode = null;
            double bestValue = Double.NEGATIVE_INFINITY;
            for (Node n : node.children) {
                double pb = 0;
                if (node.move != Board.MOVE_NONE) {
                    int firstMove = -1, secondMove = -1;
                    //First, get the firstMove and secondMove, depending on syncMoves
                    if (this.syncMoves) {
                        if (node.depth % 2 == 0) {
                            if (node.parent != null) {
                                if (node.parent.parent != null) {
                                    secondMove = node.parent.parent.playerPosition;
                                    if (node.parent.parent.parent != null) {
                                        firstMove = node.parent.parent.parent.playerPosition;
                                    }
                                }

                            }
                        } else {
                            secondMove = node.playerPosition;
                            if (node.parent != null) {
                                if (node.parent.parent != null) {
                                    if (node.parent.parent.parent != null) {
                                        firstMove = node.parent.parent.parent.playerPosition;
                                    }
                                }
                            }
                        }
                    } else {
                        if (node.parent != null) {
                            firstMove = node.parent.playerPosition;
                        }
                        secondMove = node.playerPosition;
                    }

                    //Set up a list with all the validmoves.
                    ArrayList<Integer> validMoves = new ArrayList<Integer>();
                    for (int i = 0; i < node.children.size(); i++) {
                            validMoves.add(node.children.get(i).playerPosition);
                    }

                    //Get the heuristic value for this situation.
                    int move = -1;
                    if (firstMove != -1 && secondMove != -1) {
                        pb = (W * this.tables.getHeuristicValue(firstMove, secondMove, n.playerPosition)) / (n.visits - n.draws - n.wins + 1.0);
                    }                   
                }
                double uct = n.value / (n.visits + 1.0) + C * Math.sqrt(Math.log(node.visits + 1.0) / (n.visits + 1.0)) + pb;

                if (uct > bestValue) {
                    bestNode = n;
                    bestValue = uct;
                }
            }
            return bestNode;
        }

        @Override
        public String toString() {
            return "LGRPBUCT";
        }
    }
}
